package com.killer.tree;

import com.killer.linear.MyLinkedQueue;
import com.killer.linear.MyLinkedStack;
import com.killer.linear.MyQueue;
import com.killer.linear.MyStack;

/**
 * 二叉查找树
 */
public class BinarySearchTree<T extends Comparable> implements Tree<T>{

    /**
     * 根节点
     */
    TreeNode<T> root;

    /**
     * 往树增加节点
     */
    public void add(T data){
        TreeNode<T> node = new TreeNode<T>(data);
        //判断头结点是否为空
        if (root == null) {
            root=node;
            return;
        }
        root.insert(node);
    }

    public void preTraverse() {
        preTraverse(root);
        System.out.println();

    }

    private void preTraverse(TreeNode<T> root) {
        //先根,再左,再右
        if (root == null) {
            return;
        }
        //遍历根
        System.out.print(root.data+" ");
        //遍历左节点
        preTraverse(root.leftChild);
        //遍历右节点
        preTraverse(root.rightChild);
    }

    public void midTraverse() {
        midTraverse(root);
        System.out.println();
    }

    private void midTraverse(TreeNode<T> root) {
        if (root == null) {
            return;
        }
        //遍历左节点
        midTraverse(root.leftChild);
        //遍历根
        System.out.print(root.data+" ");
        //遍历右节点
        midTraverse(root.rightChild);
    }

    public void backTraverse() {
        backTraverse(root);
        System.out.println();
    }


    private void backTraverse(TreeNode<T> root) {
        if (root == null) {
            return;
        }
        //遍历左节点
        backTraverse(root.leftChild);
        //遍历右节点
        backTraverse(root.rightChild);
        //遍历根
        System.out.print(root.data+" ");
    }


    public void boradTraverse() {
        if (root == null) {
            return;
        }
        //创建一个队列,利用队列进行宽搜遍历
        MyQueue<TreeNode> queue=new MyLinkedQueue<TreeNode>();
        //根节点入队列
        queue.offer(root);
        //一直到队列为空位置
        while (queue.size() > 0) {
            //队列的首部出队
            TreeNode node = queue.poll();
            System.out.print(node.data+" ");
            //判断该节点是否有孩子点
            if (node.leftChild != null) {
                //有的话将左孩子入队
                queue.offer(node.leftChild);
            }
            //判断该节点是否有右孩子
            if (node.rightChild != null) {
                //有的话将右孩子入队
                queue.offer(node.rightChild);
            }
        }
    }

    protected class TreeNode<T extends Comparable> {

        /**
         * 数据域
         */
        T data;

        /**
         * 左孩子
         */
        TreeNode<T> leftChild;

        /**
         * 右孩子
         */
        TreeNode<T> rightChild;

        /**
         * 父节点
         */
        TreeNode<T> parent;

        public TreeNode(T data) {
            this.data = data;
        }

        public void insert(TreeNode<T> node) {
            //跟父节点比较
            if (node.data.compareTo(this.data) < 0) {
                //如果插入的节点小于当前节点,则往左边插入
                if (this.leftChild == null) {
                    this.leftChild=node;
                    //设置父节点
                    node.parent=this;
                }else{
                    this.leftChild.insert(node);
                }
            }else{
                //否则往右边插入
                if (this.rightChild == null) {
                    this.rightChild=node;
                    //设置父节点
                    node.parent=this;
                }else{
                    this.rightChild.insert(node);
                }
            }
        }
    }
}
